class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 新增节点的高度初始化为1

class AVLTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        if not self.root:
            self.root = TreeNode(key)
        else:
            self.root = self._insert(self.root, key)
    
    def _insert(self, node, key):
        # 1. 执行标准的BST插入
        if not node:
            return TreeNode(key)
        elif key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)
        
        # 2. 更新节点高度
        node.height = 1 + max(self._get_height(node.left), 
                             self._get_height(node.right))
        
        # 3. 获取平衡因子
        balance = self._get_balance(node)
        
        # 4. 如果节点不平衡，尝试4种旋转情况
        # 情况1 - 左左
        if balance > 1 and key < node.left.key:
            return self._right_rotate(node)
        
        # 情况2 - 右右
        if balance < -1 and key > node.right.key:
            return self._left_rotate(node)
        
        # 情况3 - 左右
        if balance > 1 and key > node.left.key:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)
        
        # 情况4 - 右左
        if balance < -1 and key < node.right.key:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)
        
        return node
    
    def delete(self, key):
        if not self.root:
            return
        self.root = self._delete(self.root, key)
    
    def _delete(self, node, key):
        # 1. 执行标准BST删除
        if not node:
            return node
        
        elif key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            # 有1个或0个子节点的情况
            if node.left is None:
                temp = node.right
                node = None
                return temp
            elif node.right is None:
                temp = node.left
                node = None
                return temp
            
            # 有2个子节点的情况: 获取中序后继(右子树的最小值)
            temp = self._get_min_value_node(node.right)
            node.key = temp.key
            node.right = self._delete(node.right, temp.key)
        
        # 如果树只有一个节点，直接返回
        if node is None:
            return node
        
        # 2. 更新节点高度
        node.height = 1 + max(self._get_height(node.left),
                            self._get_height(node.right))
        
        # 3. 获取平衡因子
        balance = self._get_balance(node)
        
        # 4. 如果节点不平衡，尝试4种旋转情况
        # 情况1 - 左左
        if balance > 1 and self._get_balance(node.left) >= 0:
            return self._right_rotate(node)
        
        # 情况2 - 右右
        if balance < -1 and self._get_balance(node.right) <= 0:
            return self._left_rotate(node)
        
        # 情况3 - 左右
        if balance > 1 and self._get_balance(node.left) < 0:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)
        
        # 情况4 - 右左
        if balance < -1 and self._get_balance(node.right) > 0:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)
        
        return node
    
    def _left_rotate(self, z):
        y = z.right
        T2 = y.left
        
        # 执行旋转
        y.left = z
        z.right = T2
        
        # 更新高度
        z.height = 1 + max(self._get_height(z.left),
                          self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left),
                          self._get_height(y.right))
        
        # 返回新的根节点
        return y
    
    def _right_rotate(self, z):
        y = z.left
        T3 = y.right
        
        # 执行旋转
        y.right = z
        z.left = T3
        
        # 更新高度
        z.height = 1 + max(self._get_height(z.left),
                          self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left),
                          self._get_height(y.right))
        
        # 返回新的根节点
        return y
    
    def _get_height(self, node):
        if not node:
            return 0
        return node.height
    
    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)
    
    def _get_min_value_node(self, node):
        if node is None or node.left is None:
            return node
        return self._get_min_value_node(node.left)
    
    def pre_order(self):
        self._pre_order(self.root)
        print()
    
    def _pre_order(self, node):
        if node:
            print(node.key, end=" ")
            self._pre_order(node.left)
            self._pre_order(node.right)
    
    def in_order(self):
        self._in_order(self.root)
        print()
    
    def _in_order(self, node):
        if node:
            self._in_order(node.left)
            print(node.key, end=" ")
            self._in_order(node.right)
    
    def post_order(self):
        self._post_order(self.root)
        print()
    
    def _post_order(self, node):
        if node:
            self._post_order(node.left)
            self._post_order(node.right)
            print(node.key, end=" ")

# 测试代码
if __name__ == "__main__":
    avl = AVLTree()
    keys = [10, 20, 30, 40, 50, 25]
    
    for key in keys:
        avl.insert(key)
    
    print("前序遍历:")
    avl.pre_order()  # 预期输出: 30 20 10 25 40 50
    
    print("中序遍历:")
    avl.in_order()   # 预期输出: 10 20 25 30 40 50
    
    print("后序遍历:")
    avl.post_order() # 预期输出: 10 25 20 50 40 30
    
    print("\n删除节点 10")
    avl.delete(10)
    avl.in_order()   # 预期输出: 20 25 30 40 50
    
    print("\n删除节点 40")
    avl.delete(40)
    avl.in_order()   # 预期输出: 20 25 30 50